//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表
// 二叉搜索树的左子树的节点都小于根节点 右子树的节点有大于根节点
//1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后
// 树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
//2.返回链表中的第一个节点的指针
//3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
//4.你不用输出双向链表，程序会根据你的返回值自动打印输出

import java.util.ArrayList;
import java.util.List;


public class Solution {
    public class TreeNode {
        Solution.TreeNode left = null;
        Solution.TreeNode right = null;
        int val = 0;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    //返回的第一个指针，即为最小值，先定为null
    public TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            //中序递归，叶子为空则返回
            return null;
        //首先递归到最左最小值
        Convert(pRootOfTree.left);
        //找到最小值，初始化head与pre
        //如果pre为null，说明当前节点是链表的第一个节点，
        if(pre == null){
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //当前节点与上一节点建立连接，将pre设置为当前值
        //如果pre不为null，说明当前节点不是链表的第一个节点
        // 需要将前一个节点pre的右指针指向当前节点，并将当前节点的左指针指向pre
        else{
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}













